package algorithm.union;

/**
 * @author bingo
 * @Date 2018/3/10
 */
public class UnionFind1 {

    private int[] id;

    private int count;

    public UnionFind1(int n) {
        id = new int[n];
        this.count = n;
        for(int i=0;i<n;i++){
            id[i]=i;
        }

    }

    public int find(int p){
        assert p >= 0 && p < count;
       return  id[p];
    }

    public boolean isConnected(int p,int q){

        return  find(p)==find(q);
    }

    public void unionElements(int p, int q){

        int pID = find(p);
        int qID = find(q);

        if(pID==qID){
            return;
        }

        for(int i=0;i<count;i++){
            if(id[i] == pID){
                id[i] = qID;
            }
        }
    }

    public int[] getId() {
        return id;
    }

    public void setId(int[] id) {
        this.id = id;
    }

    /**
 *
 *        0  1 2 3 4 5 6 7 8 9
 *
 * 输入:  0  1
 *
 *       pid = 0;    qid = 1
 *
 *      id[0]=1;
 *
 *      1 1 2 3 4 5 6 7 8 9
 *
 *
 */



    public static void main(String[] args) {

        UnionFind1 unionFind1 = new UnionFind1(10);
        for(int i=0;i<10;i++){
            System.out.print(unionFind1.id[i]+",");
        }
        System.out.println();
        unionFind1.unionElements(0,1);
        unionFind1.unionElements(1,2);
        unionFind1.unionElements(2,3);
        unionFind1.unionElements(3,4);
        unionFind1.unionElements(8,9);
        for(int i=0;i<10;i++){
            System.out.print(unionFind1.id[i]+",");
        }

    }
}
